// hard

// 给定一个字符串s，一个字符串t
// 要求返回 s中涵盖t所有字符的最小子串，如果s中不存在涵盖t所有字符的子串，则返回空字符串''


// 思路，滑动窗口

function minWindow(s, t) {
    let left = 0
    let right = 0
    const need = new Map()
    for (const c of t) {
        need.set(c, need.has(c) ? need.get(c) + 1 : 1)
    }

    let needType = need.size
    let res = ''

    while (right < s.length) {
        let c = s[right]
        if (need.has(c)) {
            need.set(c, need.get(c) - 1)
            if (need.get(c) === 0) {
                needType -= 1
            }
        }

        while (needType === 0) {
            const newRes = s.substring(left, right + 1)
            if (!res || newRes.length < res.length) {
                res = newRes
            }
            const c2 = s[left]
            if (need.has(c2)) {
                need.set(c2, need.get(c2) + 1)
                if (need.get(c2) === 1) {
                    needType += 1
                }
            }
            left += 1
        }
        right += 1
    }
    return res
}

let s = "ADOBECODEBANC", t = "ABC"
console.log(minWindow(s, t));